﻿using System;
using System.Linq;
using System.Collections.Generic;
using System.Runtime.InteropServices;

namespace ConsoleApp1
{
    class Program
    {
        static List<int> source = new List<int> { 945, 1599, 2299, 1027, 1208, 1317, 1251, 1406, 1257, 1236, 689, 877, 1824, 908, 2092, 722, 2278, 912, 831, 74, 711 };
        static int target = 5000;
        static List<a> Values = new List<a>();
        static void Main(string[] args)
        {
            for (var i = 0; i < source.Count; i++)
            {
                var value = new a
                {
                    value = source[i],
                    Str = source[i].ToString()
                };
                var newArray = source.Skip(i + 1).ToList();
                if (newArray.Count > 0)
                {
                    jisuan(value, newArray);
                }
            }

            //foreach(var item in Values)
            //{
            //    Console.WriteLine($"{item.value}    =>      {item.Str}");
            //}


            Console.WriteLine("=================================");
            Values.ForEach(p => {
                p.difference = p.value - target;
            });

           var data =  Values.OrderBy(p => p.difference).Take(5).ToList();

            foreach (var item in data)
            {
                Console.WriteLine($"{item.value}    =>      {item.Str}");
            }
        }

        static void jisuan(a value, List<int> sum)
        {
            var v = value.Clon();
            for (var i = 0; i < sum.Count; i++)
            {
                v.value += sum[i];
                v.Str += $"+{sum[i].ToString()}";
                if (value.value + sum[i] >= target)
                {
                    Values.Add(v);
                    continue;
                }
                var newArray = sum.Skip(i + 1).ToList();
                if (newArray.Count > 0)
                {
                    jisuan(v, newArray);
                }
            }
        }

        class a
        {
            public int value { get; set; }
            public string Str { get; set; } = "";

            public int difference { get; set; }

            public a Clon()
            {
                return new a
                {
                    value = value,
                    Str = Str
                };
            }
        }
    }
}
